package org.lintcode_Pattern;

/**
 * @Auther: qingle
 * @Date: 2024/8/20-23:02
 * @Description:
 * 使用条件
 * 复杂度
 * • 时间复杂度 get O(1), set O(1)
 * • 空间复杂度 O(n)
 * 炼码例题
 * • LintCode 134. LRU 缓存
 * @version: 1.0
 */
import java.util.HashMap;
import java.util.Map;


/**
 * 在构造函数中初始化size为0。
 * 在set方法中，如果key已经存在，则直接更新值并移动节点到尾部。
 * 添加了removeHead方法来删除链表头部节点，以便于在缓存达到容量上限时使用。
 * 在set方法中，如果缓存已满，先调用removeHead方法删除一个节点，然后再次调用set方法添加新节点。
 *
 */
public class LRUCache {
	// 单链表节点
	class ListNode {
		public int key, val;
		public ListNode next;

		public ListNode(int key, int val) {
			this.key = key;
			this.val = val;
			this.next = null;
		}
	}

	// cache 的最大容量
	private final int capacity;
	// cache 当前存储的容量
	private int size;
	// 单链表的 dummy 头
	private final ListNode dummy;
	// 单链表尾
	private ListNode tail;
	// key 映射到数据节点的前一个节点
	private final Map<Integer, ListNode> keyToPrev;

	// 构造函数
	public LRUCache(int capacity) {
		this.capacity = capacity;
		this.keyToPrev = new HashMap<>();
		// 初始化dummy节点和tail引用
		this.dummy = new ListNode(0, 0);
		this.tail = dummy;
		this.size = 0;
	}

	// 将 key 节点移动到尾部（最近使用）
	private void moveToTail(int key) {
		ListNode prev = keyToPrev.get(key);
		ListNode curr = prev.next;

		// 如果 key 节点已经在尾部，无需移动
		if (tail == curr) {
			return;
		}

		// 从链表中删除 key 节点
		prev.next = curr.next;

		// 将curr节点链接到tail后面
		tail.next = curr;
		curr.next = null;

		// 更新尾部引用
		tail = curr;

		// 更新key映射
		keyToPrev.remove(key);
		keyToPrev.put(key, tail);
	}

	public int get(int key) {
		// 如果这个 key 不存在于缓存，返回 -1
		if (!keyToPrev.containsKey(key)) {
			return -1;
		}

		// 这个 key 刚刚被访问过，因此 key 节点应当被移动到链表尾部
		moveToTail(key);

		// 返回尾部节点的值
		return tail.val;
	}

	public void set(int key, int value) {
		// 如果 key 已经存在，更新 keyNode 的 value
		if (keyToPrev.containsKey(key)) {
			ListNode prev = keyToPrev.get(key);
			prev.next.val = value;
			moveToTail(key);
			return;
		}

		// 如果 key 不存在于 cache 且 cache 未超上限
		if (size < capacity) {
			size++;
			ListNode newNode = new ListNode(key, value);
			// 插入到链表尾部
			tail.next = newNode;
			newNode.next = null;
			tail = newNode;
			keyToPrev.put(key, tail);
		} else {
			// 如果超过上限，删除链表头部节点
			removeHead();
			// 添加新节点到尾部
			set(key, value);
		}
	}

	// 删除链表头部节点
	private void removeHead() {
		ListNode first = dummy.next;
		keyToPrev.remove(first.key);
		dummy.next = first.next;
		if (dummy.next != null) {
			keyToPrev.put(dummy.next.key, dummy);
		}
	}
}